
local Map = {}
local Mapw = map("xsize")+1
local Maph = map("ysize")+1
for i=0,Mapw*Maph do
	Map[i] = tile(i%Mapw,math.floor(i/Mapw),"walkable")
end
local abs = math.abs

moba.pathfinding_inradius = function(sx,sy,dx,dy,r)
	return (sx-dx)*(sx-dx)+(sy-dy)*(sy-dy) < r*r
end

--heuristics
moba.pathfinding_manhattan = function(sx,sy,dx,dy)
	return abs(sx-dx)+abs(sy-dy)
end
moba.pathfinding_euclidean = function(sx,sy,dx,dy)
	return (sx-dx)*(sx-dx)+(sy-dy)*(sy-dy)
end

astar = function(sx,sy,dx,dy,freetile)
	open = {}
	closed = {}
	freetile = freetile or function() return true end
	local heuristic = moba.pathfinding_manhattan
	
	if sx==dx and sy==dy then return nil end
	if not freetile(dx,dy) then return nil end
	
	local TILE = sy*Mapw+sx
	closed[TILE] = {
		G = 0,
		H = heuristic(sx,sy,dx,dy)
	}
	
	while(TILE ~= dy*Mapw+dx) do
		--for all of the adjacent tiles
		for x=sx-1,sx+1,1 do
			for y=sy-1,sy+1,1 do
				--(don't read the current node)
				if not(x==sx and y==sy) then
					--(check bounds)
					if x >= 0 and x < Mapw then
						local ITER = y*Mapw+x
						--tile inbounds and not in closed list
						if Map[ITER] and not closed[ITER] then
							--don't walk through walls diagonally
							if (x==sx or y==sy) or (Map[sy*Mapw+x] and Map[y*Mapw+sx] and freetile(x,sy) and freetile(sx,y)) then
								if freetile(x,y) then
									local nextg = closed[TILE].G+((x==sx or y==sy) and 1 or 2^0.5)
									if open[ITER] then
									--did we find a shorter path to an already calculated node?
										if open[ITER].G > nextg then
											--overwrite
											open[ITER].G = nextg
											open[ITER].P = TILE
										end
									else
										--calculate node's H (distance to destination) and G (distance traveled)
										open[ITER] = {
											G = nextg,
											H = heuristic(x,y,dx,dy),
											P = TILE,
										}
									end
								end
							end
						end
					end
				end
			end
		end
		
		--choose the shortest looking straight path
		local lowest = math.huge
		local NEXT = TILE
		for k,v in pairs(open) do
			if v.G + v.H < lowest then
				lowest = v.G+v.H
				NEXT = k
			end
		end
		--if open list was empty return nil
		if TILE == NEXT then return end
		--set the current tile to the chosen one
		TILE = NEXT
		sx = NEXT%Mapw
		sy = math.floor(NEXT/Mapw)
		--move it to the closed list
		closed[TILE] = open[TILE]
		open[TILE] = nil
	end
	--Trace back the path
	if TILE == dy*Mapw+dx then
		local r = {}
		r[1] = {x = TILE%Mapw, y = math.floor(TILE/Mapw)}
		local prev = closed[TILE].P
		while closed[prev].P do
			r[#r+1] = {x = prev%Mapw, y = math.floor(prev/Mapw)}
			prev = closed[prev].P
		end
		--reverse the path
		for i=1,#r/2 do
			r[i], r[#r-i+1] = r[#r-i+1], r[i]
		end
		return r
	else
		--for some reason the path's last node isn't at the end
		return
	end
end